#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class MagicDictionary
{
private:
    vector<string> dict;

public:
    MagicDictionary()
    {
        // reset
        dict = {};
    }

    void buildDict(vector<string> dictionary)
    {
        dict = dictionary;
    }

    bool search(string searchWord)
    {
        for (string d : dict)
        {
            int diff = 0;

            if (d.length() != searchWord.length())
                continue;
            for (int i = 0; i < searchWord.length() && diff < 2; i++)
            {
                cout << d << ":" << searchWord << endl;
                if (d[i] != searchWord[i])
                    diff++;
            }
            if (1 == diff)
            {
                return true;
            }
        }
        return false;
    }
};

class MagicDictionary_2
{
public:
    unordered_map<int, vector<string>> rec;
    MagicDictionary_2() {}

    void buildDict(vector<string> dictionary)
    {
        for (auto &str : dictionary)
        {
            rec[str.size()].push_back(str);
        }
    }

    bool search(string searchWord)
    {
        int diff;
        for (auto &str : rec[searchWord.size()])
        {
            diff = 0;
            for (int i = 0; i < str.size() && diff < 2; ++i)
            {
                if (str[i] != searchWord[i])
                    ++diff;
            }
            if (diff == 1)
                return true;
        }
        return false;
    }
};

/**
 * @brief trie
 *
 * @return int
 */
struct Trie
{
    bool isEnd;
    vector<Trie *> children;
    Trie() : isEnd(false), children(26, NULL) {}
    ~Trie()
    {
        for (Trie *child : children)
        {
            if (child)
                delete child;
        }
    }
};
class MagicDictionary_3
{
    Trie *root;
    void addWord(string &str)
    {
        Trie *cur = root;
        for (char &c : str)
        {
            if (cur->children[c - 'a'] == NULL)
            {
                cur->children[c - 'a'] = new Trie();
            }
            cur = cur->children[c - 'a'];
        }
        cur->isEnd = true;
    }

    bool backtracking(Trie *cur, string &word, int index, int cnt)
    {
        if (index == word.size())
        {
            if (cnt == 1 && cur->isEnd == true)
                return true;
            else
                return false;
        }
        for (int i = 0; i < 26; ++i)
        {
            // 不进入空节点
            if (cur->children[i] == NULL)
                continue;
            if ('a' + i == word[index])
            {
                if (backtracking(cur->children[i], word, index + 1, cnt))
                    return true;
            }
            else if (cnt == 0 && 'a' + i != word[index])
            {
                if (backtracking(cur->children[i], word, index + 1, cnt + 1))
                    return true;
            }
        }
        return false;
    }

public:
    /** Initialize your data structure here. */
    MagicDictionary_3()
    {
        root = new Trie();
    }

    void buildDict(vector<string> dictionary)
    {
        for (string &str : dictionary)
        {
            addWord(str);
        }
    }

    bool search(string searchWord)
    {
        Trie *cur = root;
        return backtracking(cur, searchWord, 0, 0);
    }
};
int main()
{
    /**
     * @brief
     * ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
[[], [["hello","hallo","leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
     *
     */
    MagicDictionary magic = MagicDictionary();
    vector<string> dict = {"hello", "hallo", "leetcode"};
    magic.buildDict(dict);
    cout << magic.search("helol") << endl;
    cout << magic.search("hello") << endl;
    cout << magic.search("leetcodd") << endl;
    system("pause");
    return 0;
}
